#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<windows.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<iostream>
#include<iomanip>
#include<fstream>
#include<algorithm>
#include<utility>
using namespace std;


//合并两个有序链表
//struct SListNode* mergeTwoLists(struct SListNode* list1, struct SListNode* list2)
//{
//	if(!list1)//两表一表为空的情况
//	{
//		return list2;
//	}
//	if(!list2)
//	{
//		return list1;
//	}
//
//	struct SListNode* head = (struct SListNode*)malloc(sizeof(struct SListNode));
//	struct SListNode* tail = head;
//
//	while (list1 && list2)
//	{
//		if ((list1->data) < (list2->data))
//		{
//			tail->next = list1;
//			tail = tail->next;
//			list1 = list1->next;
//		}
//		else
//		{
//			tail->next = list2;
//			tail = tail->next;
//			list2 = list2->next;
//		}
//	}
//	if (list1)
//	{
//		tail->next = list1;
//	}
//	if (list2)
//	{
//		tail->next = list2;
//	}
//
//	struct SListNode* node = head->next;
//	free(head);
//	return node;
//}

//输出链表的中间节点--OJ--头节点版
//struct SListNode* middleNode(struct SListNode* head)
//{
//	struct SListNode* guard = (struct SListNode*)malloc(sizeof(struct SListNode));
//	guard->next = head;
//	if (head->next)
//	{
//		SListNode* node = guard->next;
//		int size = 0;
//		if (node->next)//链表只有一个结点直接返回
//		{
//			while (node)//计算节点数
//			{
//				node = node->next;
//				++size;
//			}
//			node = guard->next;
//			for (int i = 0; i <= (size / 2) - 1; ++i)
//			{
//				node = node->next;
//			}
//			return node;
//		}
//		else
//		{
//			return node;
//		}
//	}
//	return NULL;
//}

//输出链表的中间节点--OJ--无头节点版
//struct SListNode* middleNode(struct SListNode* head)
//{
//	if (head)
//	{
//		SListNode* node = head;
//		int size = 0;
//		if (node->next)//链表只有一个结点直接返回
//		{
//			while (node)//计算节点数
//			{
//				node = node->next;
//				++size;
//			}
//			node = head;
//			for (int i = 0; i <= (size / 2) - 1; ++i)
//			{
//				node = node->next;
//			}
//			return node;
//		}
//		else
//		{
//			return node;
//		}
//	}
//	return NULL;
//}